package com.darwin.darwinIsometric.pathfinding
{
	import flash.geom.Point;

	/**
	 *加强版A*Star 
	 * @author Yuri
	 * 
	 */
	public class DAStar
	{
		/**
		 *	8方向 
		 */
		public static const DIRECTION_8:int = 8;
		/**
		 *	4方向 
		 */
		public static const DIRECTION_4:int = 4;
		
		/**
		 * 曼哈顿算法
		 */
		public static const MANHATTAN:String = "manhattan";
		
		/**
		 * 欧几里得 
		 */
		public static const EUCLIDIAN:String = "euclidian";
		
		/**
		 * 对角线
		 */
		public static const DIAGONAL:String = "diagonal";
		//private var _open:Array;
		private var _heuristic:Function;//算法核心函数
		private var _open:BinaryHeap;
		private var _grid:MapGrid;
		private var _endNode:ANode;
		private var _startNode:ANode;
		private var _path:Array;
		private var _direction:int;
		private var _straightCost:Number = 1.0;
		private var _diagCost:Number = Math.SQRT2;
		private var _wallCost:Number = 1000;
		
		private var nowversion:int = 1;
		/**
		 *	最大允许步数，超过这个步数会强制结束
		 */
		public var maxStep:int = 500;
		
		
		/**
		 *	当无法找到从起点到终点的完整路径时的策略
		 * <li/>0:停在原地不动
		 * <li/>1:尽可能走到离目的地最近的位置 (消耗更大)
		 */
		public var falseStrategy:int = 0;
		
		
		/**
		 *	实例化一个 二叉堆A*算法
		 * @param grid 地图数据
		 * @param direction 方向
		 * @param algorithm 算法
		 */
		public function DAStar(direction:int=DAStar.DIRECTION_8, algorithm:String=DAStar.EUCLIDIAN)
		{
			_direction = direction;
			if(algorithm == AStar.DIAGONAL)
			{
				_heuristic = diagonal;
			}else if(algorithm == AStar.EUCLIDIAN){
				_heuristic = euclidian2;
			}else{
				_heuristic = manhattan;
			}
		}
		
		private function justMin(x:Object, y:Object):Boolean {
			return x.f < y.f;
		}
		
		/**
		 *	寻路 
		 * @param grid 寻路用的地图
		 * @return 寻路是否成功
		 * 
		 */
		public function findPath(grid:MapGrid):Boolean {
			_endNode = grid.endNode;
			nowversion++;
			_startNode = grid.startNode;
			_grid = grid;
			if(_startNode==null || _endNode==null)return false;
			_open = new BinaryHeap(justMin);
			_startNode.g = 0;
			return search();
		}
		
		/**
		 *优化寻路方法减少  增加Anode层级的寻路
		 * @return 
		 * 
		 */		
		public function search():Boolean {
			var node:ANode = _startNode;
			node.version = nowversion;
			var step:int = 0;
			while (node != _endNode){
				var len:int = node.links.length;
				for (var i:int = 0; i < len; i++){
					var cost:Number = node.links[i].cost;
					if(falseStrategy == 0 && cost >= _wallCost){
						continue;
					}
					var test:ANode = node.links[i].node;
					var g:Number = node.g + cost;
					var h:Number = _heuristic(test);
					var f:Number = g + h;
					if (test.version == nowversion){
						if (test.f > f){
							test.f = f;
							test.g = g;
							test.h = h;
							test.parent = node;
						}
					} else {
						test.f = f;
						test.g = g;
						test.h = h;
						test.parent = node;
						_open.ins(test);
						test.version = nowversion;
					}
					
				}
				if (_open.a.length == 1){
					return false;
				}
				node = _open.pop() as ANode;
				step++;
				if(step>maxStep && falseStrategy==0) return false;
			}
			buildPath();
			if(falseStrategy==1)
			{
				for (var k:int = 0; k < _path.length; k++) 
				{
					var n:ANode = _path[k].node;
					if(n.walkable == 0){
						_path.splice(k);
					}
				}
			}
			return true;
		}
		
		/**
		 *生成路径 
		 * 
		 */
		private function buildPath():void {
			_path = [];
			var node:ANode = _endNode;
//			_path.push(node);
			_path.push({"x":node.x + _grid.startX,"y":node.y + _grid.startY,"node":node});
			while (node != _startNode){
				node = node.parent;
//				_path.unshift(node);
				_path.unshift({"x":node.x + _grid.startX,"y":node.y + _grid.startY,"node":node});
			}
		}
		
		private function bresenhamNodes(p1:Point, p2:Point):Array {
			var steep:Boolean = Math.abs(p2.y - p1.y) > Math.abs(p2.x - p1.x);
			if (steep){
				var temp:int = p1.x;
				p1.x = p1.y;
				p1.y = temp;
				temp = p2.x;
				p2.x = p2.y;
				p2.y = temp;
			}
			var stepX:int = p2.x > p1.x ? 1 : (p2.x < p1.x ? -1 : 0);
			var stepY:int = p2.y > p1.y ? 1 : (p2.y < p1.y ? -1 : 0);
			var deltay:Number = (p2.y - p1.y) / Math.abs(p2.x - p1.x);
			var ret:Array = [];
			var nowX:Number = p1.x + stepX;
			var nowY:Number = p1.y + deltay;
			if (steep){
				ret.push(new Point(p1.y, p1.x));
			} else {
				ret.push(new Point(p1.x, p1.y));
			}
			while (nowX != p2.x){
				var fy:int = Math.floor(nowY)
				var cy:int = Math.ceil(nowY);
				if (steep){
					ret.push(new Point(fy, nowX));
				} else {
					ret.push(new Point(nowX, fy));
				}
				if (fy != cy){
					if (steep){
						ret.push(new Point(cy, nowX));
					} else {
						ret.push(new Point(nowX, cy));
					}
				}
				nowX += stepX;
				nowY += deltay;
			}
			if (steep){
				ret.push(new Point(p2.y, p2.x));
			} else {
				ret.push(new Point(p2.x, p2.y));
			}
			return ret;
		}
		
		
		/**
		 *	返回路径(必须先调用findPath方法) 
		 * @return 
		 * 
		 */
		public function get path():Array {
			return _path;
		}
		
		//=============各种算法核心函数================
		//曼哈顿算法
		private function manhattan(node:ANode):Number {
			return Math.abs(node.x - _endNode.x) + Math.abs(node.y - _endNode.y);
		}
		//曼哈顿算法2
		private function manhattan2(node:ANode):Number {
			var dx:Number = Math.abs(node.x - _endNode.x);
			var dy:Number = Math.abs(node.y - _endNode.y);
			return dx + dy + Math.abs(dx - dy) / 1000;
		}
		//欧几里得算法
		private function euclidian(node:ANode):Number {
			var dx:Number = node.x - _endNode.x;
			var dy:Number = node.y - _endNode.y;
			return Math.sqrt(dx * dx + dy * dy);
		}
		
		//欧几里德算法2
		private function euclidian2(node:ANode):Number {
			var dx:Number = node.x - _endNode.x;
			var dy:Number = node.y - _endNode.y;
			return dx * dx + dy * dy;
		}
		
		private var TwoOneTwoZero:Number = 2 * Math.cos(Math.PI / 3);
		//跳棋式欧几里德算法
		private function chineseCheckersEuclidian2(node:ANode):Number {
			var y:int = node.y / TwoOneTwoZero;
			var x:int = node.x + node.y / 2;
			var dx:Number = x - _endNode.x - _endNode.y / 2;
			var dy:Number = y - _endNode.y / TwoOneTwoZero;
			return Math.sqrt(dx * dx + dy * dy);
		}
		
		//对角线算法 
		private function diagonal(node:ANode):Number {
			var dx:Number = Math.abs(node.x - _endNode.x);
			var dy:Number = Math.abs(node.y - _endNode.y);
			var diag:Number = Math.min(dx, dy);
			var straight:Number = dx + dy;
			return _diagCost * diag + _straightCost * (straight - 2 * diag);
		}
		
	}
}